package com.example.graph30.graph;

import sun.security.krb5.internal.crypto.HmacMd5ArcFourCksumType;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description 图
 * @auther lijiewei
 * @date 2021/11/24 17:48
 */
public class Graph {

    //顶点个数
    private int v;
    // 邻接表
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    /**
     * 添加边，无向图一条边存两次
     * @param s 顶点
     * @param e 顶点
     * @return
     * @author lijiewei
     * @date   2021/11/29 17:58
     */
    public void addEdge(int s, int e) {
        adj[s].add(e);
        adj[e].add(s);
    }

    /**
     * 获取顶点 s 开始到顶点 e 路径
     * @param s 起点
     * @param e 终点
     * @return
     * @author lijiewei
     * @date   2021/11/29 18:01
     */
    public void bfs(int s, int e) {
        if(s == e) {
            return;
        }
        //visited 用来记录已经被访问的顶点，避免顶点被重复访问
        boolean[] visited = new boolean[v];
        visited[s] = true;

        //queue 是一个队列，用来存储已经被访问顶点相连的其他顶点
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);

        //prev 用来记录搜索路径,存储上一个顶点的下标
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }

        while(queue.size() != 0) {
            //与上一个顶点相连的顶点
            Integer w = queue.poll();
            //循环和 w 相连的顶点
            for (int i = 0; i < adj[w].size(); i++) {
                Integer q = adj[w].get(i);
                //还没有被访问过
                if (!visited[q]) {
                    prev[q] = w;
                    if (q == e) {
                        print(prev, s, e);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    /**
     * 递归打印
     * @param prev 搜索路径
     * @param s 顶点
     * @param e 顶点
     * @return
     * @author lijiewei
     * @date   2021/12/1 14:45
     */
    private void print(int[] prev, int s, int e) {
        if (prev[e] != -1 && e != s) {
            print(prev, s, prev[e]);
        }
        System.out.print(e + " -> ");
    }

    //是否已经找到
    boolean found = false;

    /**
     * 深度优先，获取顶点 s 开始到顶点 e 路径
     * @param s 起点
     * @param e 终点
     * @return
     * @author lijiewei
     * @date   2021/12/1 14:58
     */
    public void dfs(int s, int e) {
        found = false;
        //存储是否被访问过，避免重复访问
        boolean[] visited = new boolean[v];
        //用来记录搜索路径,存储上一个顶点的下标
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(s, e, visited, prev);
        print(prev, s, e);
    }

    /**
     * 迭代搜索路径
     * @param s 起点
     * @param e 终点
     * @param visited 已访问顶点
     * @param prev 搜索路径
     * @return
     * @author lijiewei
     * @date   2021/12/1 15:11
     */
    private void recurDfs(int s, int e, boolean[] visited, int[] prev) {
        if (found) {
            return;
        }
        visited[s] = true;
        if (s == e) {
            found = true;
            return;
        }
        //循环与s顶点相连的顶点
        for (int i = 0; i < adj[s].size(); i++) {
            Integer q = adj[s].get(i);
            if (!visited[q]) {
                prev[q] = s;
                recurDfs(q, e, visited, prev);
            }
        }

    }
}
